package first.forHuaWei.回溯;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @ClassName LC17
 * @description:
 * @author: 荣燊
 * @create: 2021-09-05 12:26
 **/
public class LC17 {
    // 回溯,重要的思想就是回退操作

    // 电话号码的字母组合,给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合
    public static List<String> letterCombinations(String digits) {
        ArrayList<String> result = new ArrayList<>();
        if (digits.length() == 0) {
            return result;
        }
        // map数组保存对应关系
        HashMap<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2',"abc");
        phoneMap.put('3',"def");
        phoneMap.put('4',"ghi");
        phoneMap.put('5',"jkl");
        phoneMap.put('6',"mno");
        phoneMap.put('7',"pqrs");
        phoneMap.put('8',"tuv");
        phoneMap.put('9',"wxyz");
        backTrack(result, phoneMap, digits, 0, new StringBuffer());
        return result;
    }

    // 回溯的重点就是加入之后，下一步记得释放
    public static void backTrack(List<String> res, Map<Character, String> phoneMap,
                                         String digits, int index, StringBuffer str) {
        if (index == digits.length()) {
            res.add(str.toString());
        } else {
            char c = digits.charAt(index);
            String s = phoneMap.get(c);
            int length = s.length();
            for (int i=0; i<length; i++) {
                str.append(s.charAt(i));
                backTrack(res, phoneMap, digits, index+1, str);
                str.deleteCharAt(index); // 删除就是回溯回去
            }
        }

    }
}
